package com.duoduo.剑指Offer;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @description: 最小的k个数36
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 *
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 *
 * @author: chaidl  ！
 * @create: 2022-05-28 19:29
 */
public class 最小的k个数36 {
	public static void main(String[] args) {
		int [] arr={3,2,1};
		getLeastNumbers(arr,2);
	}
	// 大根堆
	public static int[] getLeastNumbers(int[] arr, int k) {
		Arrays.sort(arr);
		//首先定义一个数组用于返回前k个数字
		int[] array = new int[k];
		if (k> arr.length || arr.length==0||k==0){
			return array;
		}
		//使用java自带的大跟堆类
		PriorityQueue<Integer> queue=new PriorityQueue<Integer>((v1, v2)->v2-v1);
		//将前k个数字添加到大跟堆里面
		for (int i = 0;i<k;i++){
			queue.offer(arr[i]);
		}
		//将第k个数字一次往大跟堆里面放，如果当前数字大于根，则跳过，小于就重新维护
		for (int i = k;i<arr.length;++i){
			if (queue.peek()>arr[i]){
				queue.poll();
				queue.offer(arr[i]);
			}
		}
		//从大跟堆里面依次取出
		for (int i = 0;i<k;i++){
			array[i]=queue.poll();
		}
		return array;
	}
}
